package com.zhaofan.other;
//给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 
//
// 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 
//
// 
//
// 示例 1： 
//
// 
//输入：p = [1,2,3], q = [1,2,3]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：p = [1,2], q = [1,null,2]
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：p = [1,2,1], q = [1,1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 两棵树上的节点数目都在范围 [0, 100] 内 
// -10⁴ <= Node.val <= 10⁴ 
// 


import java.util.LinkedList;

public class No100 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)return true;
        if(p==null||q==null) return false;
        LinkedList<TreeNode> pList = new LinkedList<>(),qList=new LinkedList<>();
        pList.push(p);
        qList.push(q);
        while(pList.size()!=0&&qList.size()!=0){
            TreeNode pNode = pList.poll();
            TreeNode qNode = qList.poll();
            if(pNode==null&&qNode==null) continue;
            if(pNode==null||qNode==null||pNode.val!=qNode.val) return false;
            pList.push(pNode.left);
            pList.push(pNode.right);
            qList.push(qNode.left);
            qList.push(qNode.right);
        }
        return true;
    }
}
